
<html>
<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=350,initial-scale=1, minimum-scale=1, maximum-scale=1, user-scalable=no"/>
    <meta name="apple-mobile-web-app-capable" content="yes" />
    <meta name="apple-mobile-web-app-status-bar-style" content="black" />
    <meta name="format-detection"content="telephone=no, email=no" />
    <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no" />
    <meta name="apple-mobile-web-app-capable" content="yes" />
    <!-- 删除苹果默认的工具栏和菜单栏 -->
    <meta name="apple-mobile-web-app-status-bar-style" content="black" />
    <!-- 设置苹果工具栏颜色 -->
    <meta name="format-detection" content="telphone=no, email=no" />
    <!-- 忽略页面中的数字识别为电话，忽略email识别 -->
    <!-- 启用360浏览器的极速模式(webkit) -->
    <meta name="renderer" content="webkit">
    <!-- 避免IE使用兼容模式 -->
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <!-- 针对手持设备优化，主要是针对一些老的不识别viewport的浏览器，比如黑莓 -->
    <meta name="HandheldFriendly" content="true">
    <!-- 微软的老式浏览器 -->
    <meta name="MobileOptimized" content="320">
    <!-- uc强制竖屏 -->
    <meta name="screen-orientation" content="portrait">
    <!-- QQ强制竖屏 -->
    <meta name="x5-orientation" content="portrait">
    <!-- UC强制全屏 -->
    <meta name="full-screen" content="yes">
    <!-- QQ强制全屏 -->
    <meta name="x5-fullscreen" content="true">
    <!-- UC应用模式 -->
    <meta name="browsermode" content="application">
    <!-- QQ应用模式 -->
    <meta name="x5-page-mode" content="app">
    <!-- windows phone 点击无高光 -->
    <meta name="msapplication-tap-highlight" content="no">
    <!-- 适应移动端end -->
</head>
<body>

<div class="Noprint" id="set" style="color: white">
    宽与高:<input type="text" style="width: 50px" value="30" id="set_w"> *  <input type="text" style="width: 50px" value="30" id="set_h"><br>
    起点坐标:(<input type="text" style="width: 50px" value="0" id="qd_x"> ,  <input type="text" style="width: 50px" value="0"  id="qd_y">)<br>
    终点坐标:(<input type="text" style="width: 50px" value="29" id="zd_x"> ,  <input type="text" style="width: 50px" value="29" id="zd_y">)<br>
    分段体积:<input type="text" style="width: 50px" value="5" id="js_bc"><br>
    <button onclick="gogo()">生成</button>
    <hr>
    <button onclick="show_way()">显示正确道路</button><button onclick="data_to()">转化</button><button onclick="print_to()">打印</button><br><br>
</div>

<div id='all' class="Noprint"></div>
<div id='way' class="Noprint"></div>
<!--startprint-->
<div id="print" style="background: #fff;
    position: absolute;
    z-index: 99;
    width: 9999px;"></div>
<!--endprint-->
</body>

<script>
    //工具方法
    var cloneObj = function (obj) {
        var newObj = {};
        if (obj instanceof Array) {
            newObj = [];
        }
        for (var key in obj) {
            var val = obj[key];
            newObj[key] = typeof val === 'object' ? cloneObj(val) : val;
        }
        return newObj;
    };
    function in_array(v,arr){
        for(var vv of arr){
            if(vv === v)return true;
        }
        return false;
    }
</script>
<script>
    let mg= [];
	let set={};
    let is_show_way=false;

    function print_to(){
        let data = data_to();
        let html = "";
        let w = 2*data.w - 1;
        html += "<div style='float:left;height:8px;width:"+(data.w * 28 + 8)+"px;background-color:black;' ></div>";
        html += "<div style='clear:both;height: 0px' />";
        html += "<div style='float:left;height:20px;width:8px;background-color:black;' ></div>";
        for(let i=0;i<=(data.w-1)*2 + (data.h-1)*2*w;i++){
            let m = data.d[i];
            let x = i%w;
            let y = parseInt(i/w);
            let g_w=8;
            let g_h=8;
            if(x%2==0){
                g_w=20;
            }
            if(y%2==0){
                g_h=20;
            }
            if(i!==0 && x===0){
                html += "<div style='float:left;height:"+(28-g_h)+"px;width:8px;background-color:black;' ></div>";
                html += "<div style='clear:both;height: 0px' />";
                html += "<div style='float:left;height:"+g_h+"px;width:8px;background-color:black;' ></div>";
            }
            html += "<div class='pintr_gg' style='float:left;width:"+g_w+"px;height:"+g_h+"px;"+(m && m==1?"background-color:black;":"")+"'>"+(m==4?"✦":(m==5?"★":""))+"</div>";
        }
        html += "<div style='float:left;height:20px;width:8px;background-color:black;' ></div>";
        html += "<div style='clear:both;height: 0px' />";
        html += "<div style='float:left;height:8px;width:"+(data.w * 28 + 8)+"px;background-color:black;' ></div>";
        bdhtml=window.document.body.innerHTML; //获取当前页的html代码
        window.document.body.innerHTML="<div id=\"print\" style=\"background: #fff;position: absolute;z-index: 99;width: 9999px;\">"+
            html +
            "</div>";
        window.print();
        window.document.body.innerHTML=bdhtml;
    }
	function data_to(){
		let d = [];
		let dw = set.w*2 -1;
        for(var y=0;y<set.h*2 -1;y++){
            for(var x=0;x<set.w*2 -1;x++){
                if(x%2 + y%2 ==1 || x%2 + y%2 ==2){
                    d[(x+y*dw)] = 1
                }
            }
        }
            for(let m of mg){
                if(in_array('真路',m.mk)){
					d[m.x*2 + m.y*2*dw]=3;
				}
                for(var w of m.way){
                    let wm = mg[w];
                    if(wm){
						if(wm.x<m.x)d[m.x*2 + m.y*2*dw - 1]=0;
						if(wm.x>m.x)d[m.x*2 + m.y*2*dw + 1]=0;
						if(wm.y<m.y)d[m.x*2 + m.y*2*dw - set.w*2 +1]=0;
						if(wm.y>m.y)d[m.x*2 + m.y*2*dw + set.w*2 -1]=0;
                    }
                }
            }
		d[mg[set.zd].x*2 + mg[set.zd].y*2*dw]=5;
		d[mg[set.qd].x*2 + mg[set.qd].y*2*dw]=4;
		//1墙 0清空标记 3标记路 4起点 5终点
        let data= {
            "w": set.w,
            "h": set.h,
            "zd": [
                mg[set.zd].x,
                mg[set.zd].y
            ],
            "qd": [
                mg[set.qd].x,
                mg[set.qd].y
            ],
            "d": d
        };
		console.log(data);
		return data;
	}
    function show_way() {
        if(is_show_way){
            is_show_way = false;
            document.getElementById('way').innerHTML = '';
        }else{
            is_show_way = true;
            let html = "";
            for(let m of mg){
                if(!in_array('真路',m.mk))continue;
                for(var w of m.way){
                    let wm = mg[w];
                    if(wm){
                        if(!in_array('真路',wm.mk))continue;
                        let m1=m;
                        let m2=wm;
                        if(wm.d<m.d){
                            m1=wm;
                            m2=m;
                        }
                        html += "<div class='way' style='top: "+(m1.y*15+2)+"px;left: "+(m1.x*15+2)+"px;width: "+(8+(m2.x - m1.x)*15)+"px;height: "+(8+(m2.y - m1.y)*15)+"px;'></div>";
                    }
                }
            }
            document.getElementById('way').innerHTML = html;
        }

    }
    function gogo(){
        set = {
            w:document.getElementById('set_w').value -1 +1,
            h:document.getElementById('set_h').value -1 +1,
            qd:0,
            zd:1
        };
        let qd_x = parseInt(document.getElementById('qd_x').value -1 +1);
        let qd_y = parseInt(document.getElementById('qd_y').value -1 +1);
        let zd_x = parseInt(document.getElementById('zd_x').value -1 +1);
        let zd_y = parseInt(document.getElementById('zd_y').value -1 +1);
        if(
            qd_x>=set.w || qd_x<0 ||
            zd_x>=set.w || zd_x<0 ||
            qd_y>=set.h || zd_x<0 ||
            zd_y>=set.h || zd_y<0
        ){
            alert('起点或终点坐标系设置错误');
            return;
        }
        set.qd = qd_x + qd_y * set.w;
        set.zd = zd_x + zd_y * set.w;
        let js_bc = document.getElementById('js_bc').value -1 +1;
        init(set,js_bc);

    }



    function init(set,js_bc){
        mg= [];
        for(let x=0;x<set.w;x++){
            for(let y=0;y<set.h;y++){
                let mk=[];
                if(x===0)mk.push('左边');
                if(x===set.w-1)mk.push('右边');
                if(y===0)mk.push('上边');
                if(y===set.h-1)mk.push('下边');
                if(x+y*set.w===set.qd)mk.push('路');
                if(x+y*set.w===set.qd)mk.push('起点');
                if(x+y*set.w===set.zd)mk.push('终点');

                mg[x+y*set.w]={
                    x:x,
                    y:y,
                    d:x+y*set.w,
                    mk:mk,
                    way:[]
                };
            }
        }

        function 画出迷宫(mg){

            let html = "";

            for(let m of mg){
                html += "<div id='gg_"+(m.d)+"' class='gg "+m.mk.join(' ')+"' style='top: "+(m.y*15)+"px;left: "+(m.x*15)+"px;'></div>";
                for(var w of m.way){
                    let wm = mg[w];
                    if(wm){
                        let m1=m;
                        let m2=wm;
                        if(wm.d<m.d){
                            m1=wm;
                            m2=m;
                        }
                        html += "<div class='way' style='top: "+(m1.y*15+2)+"px;left: "+(m1.x*15+2)+"px;width: "+(8+(m2.x - m1.x)*15)+"px;height: "+(8+(m2.y - m1.y)*15)+"px;'></div>";
                    }
                }
            }

            document.getElementById('all').innerHTML = html;
        }


        function 随机出路(this_mg){
            if(this_mg.set.qd === this_mg.set.zd){
                return this_mg.mg;
            }
            //可以取模板不?

            //
            let qd = this_mg.mg[this_mg.set.qd];
            let zd = this_mg.mg[this_mg.set.zd];


            let may_fx = [];
            if(!in_array('左边',qd.mk)){
                let d = this_mg.mg[this_mg.set.qd-1];
                if(!in_array('路',d.mk))may_fx.push(d);
            }
            if(!in_array('右边',qd.mk)){
                let d = this_mg.mg[this_mg.set.qd+1];
                if(!in_array('路',d.mk))may_fx.push(d);
            }
            if(!in_array('上边',qd.mk)){
                let d = this_mg.mg[this_mg.set.qd-this_mg.set.w];
                if(!in_array('路',d.mk))may_fx.push(d);
            }
            if(!in_array('下边',qd.mk)){
                let d = this_mg.mg[this_mg.set.qd+this_mg.set.w];
                if(!in_array('路',d.mk))may_fx.push(d);
            }
            let l = may_fx.length;
            for(let i=0;i<l;i++){
                let r = Math.floor(Math.random()*may_fx.length);
                let d = may_fx[r];
                may_fx.splice(r,1);

                let nm = cloneObj(this_mg.mg);
                nm[qd.d].way.push(d.d);
                nm[d.d].mk.push('路');
                let way = 随机出路({
                    set:{
                        w:this_mg.set.w,
                        h:this_mg.set.h,
                        qd:d.d,
                        zd:this_mg.set.zd
                    },
                    mg:nm
                });
                if(way){
                    return way;
                }
            }
            return false;
        }

        function 加上假路(this_mg) {
            let mg = this_mg.mg;
            let e_d_list = [];
            for(var g of mg){
                if(!in_array('路',g.mk)){
                    e_d_list.push(g.d);
                }else{
                    g.mk.push('真路');
                }
            }
            if(e_d_list.length===0)return;
            let l = e_d_list.length;
            let now_d = [];
            for(let i=0;i<l;i++) {
                let r = Math.floor(Math.random() * e_d_list.length);
                let d = e_d_list[r];
                e_d_list.splice(r, 1);

                if(in_array(d,now_d))continue;

                let qd = mg[d];
                let is_over = false;
                let this_x_d=[d];
                while (!is_over){
                    let may_fx=[];let may_fx_end=[];
                    if(!in_array('左边',qd.mk)){
                        let d = qd.d-1;
                        if(!in_array('路',mg[d].mk)){
                            may_fx.push(d);
                        }else if(in_array('真路',mg[d].mk)){
                            may_fx_end.push(d);
                        }
                    }
                    if(!in_array('右边',qd.mk)){
                        let d = qd.d+1;
                        if(!in_array('路',mg[d].mk)){
                            may_fx.push(d);
                        }else if(in_array('真路',mg[d].mk)){
                            may_fx_end.push(d);
                        }
                    }
                    if(!in_array('上边',qd.mk)){
                        let d = qd.d-this_mg.set.w;
                        if(!in_array('路',mg[d].mk)){
                            may_fx.push(d);
                        }else if(in_array('真路',mg[d].mk)){
                            may_fx_end.push(d);
                        }
                    }
                    if(!in_array('下边',qd.mk)){
                        let d = qd.d+this_mg.set.w;
                        if(!in_array('路',mg[d].mk)){
                            may_fx.push(d);
                        }else if(in_array('真路',mg[d].mk)){
                            may_fx_end.push(d);
                        }
                    }
                    if(may_fx_end.length>0 && Math.random()<0.4){
                        let er = Math.floor(Math.random() * may_fx_end.length);
                        qd.mk.push('路');qd.mk.push('假路');
                        qd.way.push(may_fx_end[er]);
                        is_over=true;
                    }else if(may_fx.length === 0){
                        qd.mk.push('路');qd.mk.push('假路');
                        is_over=true;
                        //尝试补救1
                        if(is_over){
                            for (let _i=0;_i<25;_i++){
                                let _rd =this_x_d[ Math.floor(Math.random() * this_x_d.length)];
                                let the_d = mg[_rd];
                                if(!in_array('左边',the_d.mk)){
                                    let d = the_d.d-1;
                                    if(!in_array('路',mg[d].mk) && Math.random()<0.5){
                                        is_over=false;
                                        the_d.way.push(d);
                                        qd = mg[d];
                                        now_d.push(d);
                                        this_x_d.push(d);
                                        break;
                                    }
                                }
                                if(!in_array('右边',the_d.mk)){
                                    let d = the_d.d+1;
                                    if(!in_array('路',mg[d].mk) && Math.random()<0.5){
                                        is_over=false;
                                        the_d.way.push(d);
                                        qd = mg[d];
                                        now_d.push(d);
                                        this_x_d.push(d);
                                        break;
                                    }
                                }
                                if(!in_array('上边',the_d.mk)){
                                    let d = the_d.d-this_mg.set.w;
                                    if(!in_array('路',mg[d].mk) && Math.random()<0.5){
                                        is_over=false;
                                        the_d.way.push(d);
                                        qd = mg[d];
                                        now_d.push(d);
                                        this_x_d.push(d);
                                        break;
                                    }
                                }
                                if(!in_array('下边',the_d.mk)){
                                    let d = the_d.d+this_mg.set.w;
                                    if(!in_array('路',mg[d].mk) && Math.random()<0.5){
                                        is_over=false;
                                        the_d.way.push(d);
                                        qd = mg[d];
                                        now_d.push(d);
                                        this_x_d.push(d);
                                        break;
                                    }
                                }
                            }
                        }
                        //尝试补救2
                        if(is_over){
                            let gd_rand_set = [
                                ['左边',-1],
                                ['右边',1],
                                ['上边',-this_mg.set.w],
                                ['下边',this_mg.set.w],
                            ];
                            for (let _i=0;_i<25;_i++){
                                let _rd =this_x_d[ Math.floor(Math.random() * this_x_d.length)];
                                let the_d = mg[_rd];
                                let fun = gd_rand_set[Math.floor(Math.random() * gd_rand_set.length)];
                                if(!in_array(fun[0],the_d.mk)){
                                    let d = the_d.d + fun[1];
                                    if(!in_array(d,this_x_d) && in_array('路',mg[d].mk) && Math.random()<0.5){
                                        the_d.way.push(d);
                                        is_over=true;
                                        break;
                                    }
                                }
                            }
                        }
                    }else {
                        let er = Math.floor(Math.random() * may_fx.length);
                        qd.mk.push('路');qd.mk.push('假路');
                        qd.way.push(may_fx[er]);
                        qd = mg[may_fx[er]];
                        now_d.push(may_fx[er]);
                        this_x_d.push(may_fx[er]);
                    }
                }
            }

        }


        var doing = function(){
            //3 3
            let lv1_mg = {
                set:set,
                mg:mg
            };
            let all_mg = [lv1_mg];
            let this_mg = lv1_mg;
            while(this_mg.set.h>js_bc*2 || this_mg.set.w>js_bc*2){
                let w = Math.ceil(this_mg.set.w/js_bc);
                let h = Math.ceil(this_mg.set.h/js_bc);
                let qd = Math.floor((this_mg.set.qd%this_mg.set.w)/js_bc) + w*Math.floor(Math.floor(this_mg.set.qd/this_mg.set.w)/js_bc);
                let zd = Math.floor((this_mg.set.zd%this_mg.set.w)/js_bc) + w*Math.floor(Math.floor(this_mg.set.zd/this_mg.set.w)/js_bc);


                let tmg= [];
                for(let x=0;x<w;x++){
                    for(let y=0;y<h;y++){
                        let mk=[];
                        if(x===0)mk.push('左边');
                        if(x===w-1)mk.push('右边');
                        if(y===0)mk.push('上边');
                        if(y===h-1)mk.push('下边');
                        if(x+y*w===qd)mk.push('路');
                        if(x+y*w===qd)mk.push('起点');
                        if(x+y*w===zd)mk.push('终点');

                        tmg[x+y*w]={
                            x:x,
                            y:y,
                            d:x+y*w,
                            mk:mk,
                            way:[]
                        };
                    }
                }

                let new_mg = {
                    set:{
                        w:w,
                        h:h,
                        qd:qd,
                        zd:zd
                    },
                    mg:tmg
                };
                all_mg.push(new_mg);
                this_mg = new_mg;
            }

            for(var i=all_mg.length-1;i>=0;i--){
                let this_mg = all_mg[i];
                if(i === all_mg.length-1){
                    this_mg.mg = 随机出路(this_mg);
                }else{
                    let next_lv_mg =all_mg[i+1];
                    let _d = next_lv_mg.set.qd;

                    let qd = this_mg.mg[this_mg.set.qd];
                    let zd = this_mg.mg[this_mg.set.zd];
                    let is_over = false;
                    while (!is_over){
                        let ddd = next_lv_mg.mg[_d];
                        if(!ddd){
                            console.log('bbbbb');
                            console.log(next_lv_mg);
                            console.log(next_lv_mg.mg);
                            console.log(_d);
                            return ;
                        }
                        let nddd = next_lv_mg.mg[ddd.way[0]];

                        let _zd;let __zd;
                        let _qd=(qd.x-js_bc*ddd.x) +(qd.y-js_bc*ddd.y)*js_bc;

                        let _w = (ddd.x+1)*js_bc > this_mg.set.w?this_mg.set.w%js_bc:js_bc;
                        let _h = (ddd.y+1)*js_bc > this_mg.set.h?this_mg.set.h%js_bc:js_bc;


                        if(!ddd.way[0]){
                            if(in_array('终点',ddd.mk)){
                                is_over = true;
                                _zd = (zd.x-js_bc*ddd.x) +(zd.y-js_bc*ddd.y)*js_bc;
                            }else{
                                alert('err');
                                return null;
                            }
                        }else{
                            if(ddd.x === nddd.x){
                                _zd = Math.floor(Math.random()*_w)  + (ddd.y < nddd.y?(js_bc*(js_bc-1)):0);
                                if(ddd.y < nddd.y){
                                    __zd = this_mg.set.w;
                                }else{
                                    __zd = -1*this_mg.set.w;
                                }
                            }else{
                                _zd = js_bc*Math.floor(Math.random()*_h)  + (ddd.x < nddd.x?((js_bc-1)):0);
                                if(ddd.x < nddd.x){
                                    __zd = 1;
                                }else{
                                    __zd = -1;
                                }
                            }
                        }
                        //
                        let tmg= [];
                        for(let x=0;x<js_bc;x++){
                            for(let y=0;y<js_bc;y++){
                                let mk=[];
                                if(x===0)mk.push('左边');
                                if(x===_w-1)mk.push('右边');
                                if(y===0)mk.push('上边');
                                if(y===_h-1)mk.push('下边');
                                if(x+y*js_bc===_qd)mk.push('路');
                                if(x+y*js_bc===_qd)mk.push('起点');
                                if(x+y*js_bc===_zd)mk.push('终点');

                                tmg[x+y*js_bc]={
                                    x:x,
                                    y:y,
                                    d:x+y*js_bc,
                                    mk:mk,
                                    way:[]
                                };
                            }
                        }
                        let this_mg_mk_mg = 随机出路({
                            set:{
                                w:js_bc,
                                h:js_bc,
                                qd:_qd,
                                zd:_zd
                            },
                            mg:tmg
                        });
                        if(!this_mg_mk_mg){
                            console.log('aaaaaaaaaaaaa');
                            console.log({
                                set:{
                                    w:js_bc,
                                    h:js_bc,
                                    qd:_qd,
                                    zd:_zd
                                },
                                mg:tmg
                            });
                            return ;
                        }
                        let the_zd = (this_mg_mk_mg[_zd]);
                        for(var _md of this_mg_mk_mg){
                            let the_d = ddd.x * js_bc + _md.x  +  this_mg.set.w * (ddd.y * js_bc + _md.y);
                            let the_way = (this_mg_mk_mg[_md.way[0]]);
                            if(!the_way){
                                if(in_array('终点',_md.mk)){
                                    if(!in_array('路',this_mg.mg[the_d].mk)){
                                        this_mg.mg[the_d].mk.push('路');
                                    }
                                    this_mg.mg[the_d].way = [__zd + ddd.x * js_bc + the_zd.x  +  this_mg.set.w * (ddd.y * js_bc + the_zd.y)];
                                }
                            }else{
                                let the_way_d = ddd.x * js_bc + the_way.x  +  this_mg.set.w * (ddd.y * js_bc + the_way.y);
                                if(!in_array('路',this_mg.mg[the_d].mk)){
                                    this_mg.mg[the_d].mk.push('路');
                                }
                                this_mg.mg[the_d].way = [the_way_d];
                            }
                        }

                        _d = ddd.way[0];
                        qd = this_mg.mg[__zd + ddd.x * js_bc + the_zd.x  +  this_mg.set.w * (ddd.y * js_bc + the_zd.y)];
                    }
                }
            }
            //加上假路
            加上假路(lv1_mg);

            console.log(mg);


            画出迷宫(mg);

        };

        doing();
    }
</script>


<style>
    body{
        background-color: black;
    }
    @media print {
        .Noprint {
            display: none;
        }
    }
    #all{
        -moz-user-select: none;
        -khtml-user-select: none;
        user-select: none;
        position:relative;
    }
    #way{
        position:relative;
    }
    #way .way{
        background-color: #ff8a3a;
    }
    .gg{
        position: absolute;
        top:0px;left:0px;
        border:1px solid #f00;
        width: 10px;
        height: 10px;
    }
    .pintr_gg{
        text-align: center;
        line-height: 20px;
    }
    .way{position: absolute;background-color: yellow;    z-index: 1;}
    .路{background-color: yellow;}
    .左边{border-left: 1px solid #000;}
    .右边{border-right: 1px solid #000;}
    .上边{border-top: 1px solid #000;}
    .下边{border-bottom: 1px solid #000;}
    .起点{background-color: blue;z-index: 2;}
    .终点{background-color: red;z-index: 2;}
</style>
